package com.jc.algortithms.sortMethods;

import java.util.Random;


/**
 * 选择排序
 * <p>
 * 1. 从数组中找到最小的元素，与第一个位置的元素交换
 * <p>
 * 2. 然后从第二个位置开始找，找到最小的，与第二个位置的元素交换
 * <p>
 * 3. 然后一直持续，外围的i只需遍历到倒数第二个元素，内循环就要从i开始一直遍历到最后一个元素
 * <p>
 * 时间复杂度为N^2
 */
public class SelectionSort {


    public static void sort(int a[]) {
        System.out.println("after selection sort");
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min])
                    min = j;
            }
            Sort.exch(a, i, min);
        }

    }

    public static void main(String[] args) {
        Random random = new Random();
        int a[] = new int[10];

        System.out.println(a.length + " items");
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(1000);
            System.out.println(i + " item is " + a[i]);
        }

        sort(a);

        for (int e : a) {
            System.out.printf("%5d", e);
        }

    }
}
